\subsection[基于优势邻域粗糙集处理混合有序数据的特征选择]{基于优势邻域粗糙集处理混合有序数据的特征选择\cite{CHEN2024109134}}

\subsubsection{邻域粗糙集}
关于经典粗糙集的改动, 人们倾向于对二元关系 $R$ 和粒的构造 $[x]$ 进行变化, 从而构造一种新的粗糙集, 而邻域粗糙集就是对二元关系进行改造,
经典粗糙集的二元关系为 
$$ R_B = \left\{ (x,y)\in U\times U\Big|f_l(x)=f_l(y),\forall l\in B \right\} $$
而这种关系太严格了, 必须严格相等. 有些数据, 比如考试成绩, 在一定范围内可以看做一种数据, 所以邻域粗糙集就产生了, 邻域粗糙集的二元关系为:
$$ R_B = \left\{ (x,y)\in U\times U\Big|\fan{f_B(x)-f_B(y)}\le \varepsilon \right\} $$
粒的构造与经典的相似 
$$ [x]_B = \left\{ y\Big|(x,y)\in R_B \right\} $$
上下近似也相同 
$$ \begin{gathered}
    \underline{R_B}(X) = \left\{ x\Big|[x]_B\subseteq X \right\}\\ 
    \overline{R_B}(X) = \left\{ x\Big|[x]_B\bigcap X\ne \varnothing \right\}
\end{gathered} $$

\subsubsection{优势粗糙集}
定义优势粗糙集, 要对信息系统进行改造, 使其具有序关系成为序信息系统:
\begin{defn}[序信息系统]
    给定信息系统 $(U,A\bigcup\left\{ d \right\},V,F)$ ,其中 $U=\left\{ x_1,\cdots,x_n \right\}$ 是论域, $A=\left\{ a_1,\cdots,a_m \right\}$ 是属性集, $d$ 是决策属性,
    $V=V_1\times V_2\times V_m$ 是值域, 其中 $V_i$ 是属性 $a_i$ 对应的值域, $F:U\times A\bigcup\left\{ d \right\}\to V$ 是对应法则.
    如果对于每一个 $V_i$ 来说, $\forall p,q\in V_i$ , $p,q$ 都有序关系 $p\succeq q$ 或者 $q\succeq p$, 则称信息系统 $(U,A,V,F)$ 是序信息系统.  
\end{defn}

在序信息系统里面有优势粗糙集, 他的二元关系的构造为:
$$ R_B=\left\{ (x,y)\in U\times U\Big|f_l(x)\succeq f_l(y),\forall l\in B \right\} $$
粒的构造分两种: 比 $x$ 优势的 , 比 $x$ 劣势的:
$$ \begin{gathered}
    D_B^+(x)=\left\{ y\in U\Big|(y,x)\in R_B \right\}\\ 
    D_B^-(x)=\left\{ y\in U\Big|(x,y)\in R_B \right\}
\end{gathered} $$

向上联合和向下联合:\\ 
决策 $d$ 的值域 $V_d$ 一般可以等价为 $T = \left\{ 1,2,\cdots,t \right\}$ ,所以可以对其进行划分:
$$ U/\left\{ d \right\} = Cl = \left\{ Cl_i\subseteq U\Big|i\in T \right\} $$
接下来对于 $\forall r>s\in T$ ,我们有 $Cl_r$ 要优于 $Cl_s$, 我们构造比 $Cl_r$ 优和比 $Cl_r$ 劣的论域子集:
$$ Cl_r^\succeq = \bigcup_{i\geq r}Cl_i, \qquad Cl_r^\preceq = \bigcup_{i\leq r}Cl_i $$
$x\in Cl_r^\succeq$ 意味着 $x$ 至少属于 $Cl_r$, $x\in Cl_r^\preceq$ 意味着 $x$ 最多属于 $Cl_r$.

上下近似也有两种(对上联合的, 对下联合的):
$$ \begin{aligned}
    \underline{R_B}(Cl_r^\succeq) &= \left\{ x\in U\Big|D_B^+(x)\subseteq Cl_r^\succeq \right\}\\ 
    \overline{R_B}(Cl_r^\succeq) &= \left\{ x\in U\Big|D_B^-(x)\bigcap Cl_r^\succeq \ne \varnothing \right\}
\end{aligned} $$
$$
\begin{aligned}
    \underline{R_B}(Cl_r^\preceq) &= \left\{ x\in U\Big|D_B^-(x)\subseteq Cl_r^\preceq \right\}\\ 
    \overline{R_B}(Cl_r^\preceq) &= \left\{ x\in U\Big|D_B^+(x)\bigcap Cl_r^\preceq \ne \varnothing \right\}
\end{aligned}$$

\subsubsection{文章的基础知识}

在第二节基础知识里面介绍了决策序信息系统, 基于优势的粗糙集. 我们首先看决策序信息系统, 他把决策系统的值域分成了三类: 简单数值, 集值, 区间.
\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be a decision system(DS), where $U=\left\{ x_1,x_2,\cdots,x_n \right\}$ is a non-empty and finite set of objects; 
    $C=\left\{ a_1,a_2,\cdots,a_m \right\}$ is a set of condition attributes and $d$ is a decision attribute; $V=\bigcup_{a\in C\bigcup\{D\}}V_a$ ,and 
    $V_a$ is the domain of attribute $a$ ; $f:U\times (C\times \left\{ d \right\})\to V$ is an information function.Accoring to the type of attribute ,
    different DSs can be obtained as follows.
    \begin{itemize}
        \item If the condition attribute set of a DS only includes categorical and numerical attributes, then we refer to such a DS as a single-valued DS 
        and record it as $\left( U,C_G\bigcup \left\{ d \right\},V,f \right)$ in the paper.
        \item If the domain of each condition attribute of a DS is a set of interval values, then the DS is called an interval-valued DS, denoted by 
        $(U,C_I\bigcup\left\{ d \right\},V,f)$ .For any $x\in U$ and $a\in C_I$ ,
        $$ f(x,a)=[a_L(x),a_U(x)]=\left\{ p\Big|a_L(x)\le p\le a_U(x),a_L(x),a_U(x)\in \mathbb{R}  \right\} $$
        where $a_L(x)$ and $a_U(x)$ are the lower and upper boundaries of $f(x,a)$ ,respectively.
        \item If the domain of each condition attribute of a DS is a family of sets, then the DS is called a set-valued DS, denoted by 
        $(U,C_S\bigcup\left\{ d \right\},V,f)$ .For any $x\in U$ and $a\in C_S$ ,$|f(x,a)|\geq 1$, where $|\cdot|$ is the cardinality of a set. 
    \end{itemize}
\end{defn}

定义好了三种类型的值域, 接下来就可以定义关系和粒了:

\begin{defn}
    In an ODS $(U,C\bigcup \left\{ d \right\},V,f)$ , for any criterion $a\in C\bigcup \left\{ d \right\}$ ,there exists an outranking relation 
    ``$\succeq$'' on the universe of discourse $U$ . For any $x,y\in U$ , $f(x,a)\succeq f(y,a)$ indicates that $x$ is at least as good as $y$ 
    w.r.t. $a$ . For convenience and without loss of generality, the paper only considers the criteria with increasing preference. The statement 
    $f(x,a)\succeq f(y,a)$ has different specific forms in different ODSs. Therefore , different dominance relations and dominating and dominated sets 
    can be obtained.
    \begin{itemize}
        \item Let $(U,C_G\bigcup \left\{ d \right\}V,f)$ be an SODS and $B\subseteq C_G$ .The dominance relation induced by $B$ is defined as 
        $$ D_B^\succeq =\left\{ (x,y)\in U\times U\Big|f(x,a)\ge f(y,a),\forall a\in B \right\} $$
        The dominating and dominated sets of $x\in U$ are defined as 
        $$ \begin{aligned}
            D^+_B(x)&=\left\{ y\in U\Big|(y,x)\in D_B^\succeq \right\} \\ 
            D^-_B(x)&=\left\{ y\in U\Big|(x,y)\in D_B^\succeq \right\} 
        \end{aligned}$$
        The dominating and dominated sets of $x$ are the sets of objects that dominate $x$ and the sets of objects that are dominated by $x$ ,respectively.

        \item Let $(U,C_I\bigcup \left\{ d \right\},V,f)$ be an IvODS and $B\subseteq C_I$ .The dominance relation induced by $B$ is defined as 
        $$ I_B^\succeq=\left\{ (x,y)\in U\times U\Big|a_L(x)\ge a_L(y),a_U(x)\ge a_U(y),\forall a\in B \right\}. $$
        The dominating and dominated sets of $x\in U$ w.r.t. $B$ are defined as 
        $$ \begin{aligned}
            I_B^+(x)&=\left\{ y\in U\Big|(y,x)\in I_B^\succeq \right\}\\ 
            I_B^-(x)&=\left\{ y\in U\Big|(x,y)\in I_B^\succeq \right\}
        \end{aligned} $$

        \item Let $(U,C_S\bigcup\left\{ d \right\},V,f)$ be an SvODS and $B\subseteq C_S$ .The dominance relation induced by $B$ is defined as 
        $$ S_B^\succeq = \left\{ (x,y)\in U\times U\Big|f(x,a)\supseteq f(y,a),\forall a\in B \right\}. $$
        The dominating and dominated sets of $x\in U$ w.r.t. $B$ are defined as 
        $$ \begin{aligned}
            S_B^+(x)&=\left\{ y\in U\Big|(y,x)\in S_B^\succeq \right\}\\ 
            S_B^-(x)&=\left\{ y\in U\Big|(x,y)\in S_B^\succeq \right\}
        \end{aligned} $$
    \end{itemize}
\end{defn}

这么看来, 这些序关系符合我们的常识, single-value 的就是普通的大于等于关系; 区间值的是左边大于左边,右边大于右边; 集值的就是包含关系.

接下来就是上联合下联合和上下近似

\begin{defn}
    In an ODS $(U,C\bigcup\left\{ d \right\},V,f)$ ,the partition on $U$ induced by the decision criterion $d$ is $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ ,
    where $C_i=\left\{ x\in U\Big|f(x,d)=i \right\}$ and $i\in \left\{ 1,2,\cdots,r \right\}$ .For any $s,t\in \left\{ 1,2,\cdots,r \right\}$ ,if $t>s$ ,
    then the objects in $C_t$ are preferred to the objects in $C_s$ . The target concepts to be approximated are the upward and downward unions of 
    decision classes, i.e., $C_i^\succeq=\bigcup_{r\ge s\ge i}C_s$ and $C_i^\preceq = \bigcup_{1\le s\le i}C_s$ ,where $i\in \left\{ 1,2,\cdots,r \right\}$ .
    The statement $x\in C_i^\succeq$  means that the decision of $x$ is no worse than $i$ ,while $x\in C_i^\preceq$ means that the decision of $x$ is no better 
    than $i$ . 
\end{defn}

\begin{defn}
    Let $(U,C_G\bigcup\left\{ d \right\},V,f)$ be an SODS, $B\subseteq C_G$ ,and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .For any 
    $i\in \left\{ 1,2,\cdots,r \right\}$ ,the lower and upper approximated of $C_i^\succeq$ w.r.t. $B$ are defined as 
    $$ \begin{aligned}
        \underline{D_B^\succeq}(C_i^\succeq)&=\left\{ x\in U\Big|D_B^+(x)\subseteq C_i^\succeq \right\}\\ 
        \overline{D_B^\succeq}(C_i^\succeq)&=\left\{ x\in U\Big|D_B^-(x)\bigcap C_i^\succeq \right\}\\ 
    \end{aligned} $$
    The pair $\left( \underline{D_B}^\succeq(C_i^\succeq),\overline{D_B^\succeq}(C_i^\succeq) \right)$ is called a DRS of $C_i^\succeq$. 
\end{defn}

\begin{defn}
    Let $(U,C_G\bigcup\left\{ d \right\},V,f)$ be an SODS, $B\subseteq C_G$ ,and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .For any 
    $i\in \left\{ 1,2,\cdots,r \right\}$ ,the lower and upper approximated of $C_i^\preceq$ w.r.t. $B$ are defined as 
    $$ \begin{aligned}
        \underline{D_B^\succeq}(C_i^\preceq)&=\left\{ x\in U\Big|D_B^-(x)\subseteq C_i^\preceq \right\}\\ 
        \overline{D_B^\succeq}(C_i^\preceq)&=\left\{ x\in U\Big|D_B^+(x)\bigcap C_i^\preceq \right\}\\ 
    \end{aligned} $$
    The pair $\left( \underline{D_B}^\succeq(C_i^\preceq),\overline{D_B^\succeq}(C_i^\preceq) \right)$ is called a DRS of $C_i^\preceq$. 
\end{defn}

对于 $(U,C_I\bigcup\left\{ d \right\},V,f)$ 和 $(U,C_S\bigcup\left\{ d \right\},V,f)$ 也是一样的

\subsubsection{混合有序决策系统中基于优势的邻域粗糙集}
首先先定义好混合有序决策信息系统(Hybrid Ordered Decision Systems,HODS)
\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, where $U,d,V$ and $f$ have the same meanings as those in ODSs, and $C=\bigcup C_k$ 
    ($k\in \left\{ G,I,S \right\}$ )is a set composed of single-valued, interval-valued, and set-valued criteria.
\end{defn}

接下来要对值域做一些规范化处理
\begin{defn}
    In an HODS $(U,C\bigcup \left\{ d \right\},V,f)$ ,for any $x\in U$ and $a\in C$ ,the normalization of $f(x,a)$ is depicted as follows.
    \begin{itemize}
        \item \textbf{Normalization of numerical criterion values}
        Suppose that $a\in C_G$ and $a$ is a numerical criterion. The normalization of $f(x,a)$ is 
        $$ f'(x,a)=\frac{f(x,a)-\min(V_a)}{\max(V_a)-\min(V_a)} $$,
        where $\max(V_a)$ and $\min(V_a)$ are the maximum and minimun of $V_a$ ,respectively.
        \item \textbf{Normalization of categorical criterion values}
        Suppose that the domain of a categorical criterion $a\in C_G$ is $V_a=\left\{ v_a^1,v_a^2,\cdots,v_a^s \right\}$ ,where s is the cardinality
        of $V_a$ and $v_a^1\succ v_a^2 \succ \cdots \succ v_a^s$. $f(x,a)=v_a^j$ is normalized by the formula
        $$ f'(x,a)=\frac{j-1}{s-1} $$ 
        \item \textbf{Normalization of interval criterion values}
        Assume that $a\in C_I$ . The normalization of $f(x,a)=[a_L(x),a_U(x)]$ is $f'(x,a)=[a_L'(x),a_U'(x)]$ ,and 
        $$ \begin{aligned}
            a_L'(x)&=\frac{a_L(x)-min(V_a^L\bigcup V_a^U)}{\max(V_a^L\bigcup V_a^U)-\min(V_a^L\bigcup V_a^U)}\\ 
            a_U'(x)&=\frac{a_U(x)-min(V_a^L\bigcup V_a^U)}{\max(V_a^L\bigcup V_a^U)-\min(V_a^L\bigcup V_a^U)}
        \end{aligned} $$
        where $V_a^L$ and $V_a^U$ are the sets of lower and upper boundaries of all the interval values in $V_a$ ,respectively.
    \end{itemize}
\end{defn}

因为是邻域粗糙集模型, 有邻域的概念, 所以就要引入距离, 对于不同类型的属性要定义不同的距离:

\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, $x,y\in U$ ,and $a\in C$ .The dominance distance between $x$ and $y$ w.r.t. $a$ is defined as 
    $$ \Delta_{a}(x,y)=\left\{
                \begin{aligned}{cl}
            f(x,a)-f(y,a),                                                  &\text{ if } a\in C_{G} \text{ and } (x,y)\in D_{\{a\}}^{\succeq},\\
            \frac{\left((a_{L}(x)-a_{L}(y))+(a_{U}(x)-a_{U}(y))\right)}{2}, &\text{ if } a\in C_{I} \text{ and } (x,y)\in I_{\{a\}}^{\succeq},\\
            \frac{|f(x,a)-f(y,a)|}{|f(x,a)|},                               &\text{ if } a\in C_{S} \text{ and } (x,y)\in S_{\{a\}}^{\succeq},\\
            -\infty,                                                        &otherwise.
        \end{aligned}\right. 
        $$
\end{defn}


接下来定义优势邻域关系(neighborhood dominance relation,NDR):
    
\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS and $B\subseteq C$ .The NDR w.r.t. $B$ is defined as 
    $$ \delta^\succeq_B=\left\{ (x,y)\in U\times U\Big|x=y\vee\Delta_a(x,y)\ge \delta,\forall a\in B \right\} $$
    where $\delta\ge 0$ is the neighborhood radius.
\end{defn}

一般的邻域粗糙集是邻域小于某个值, 但是这个是大于某个值, 这是因为他的想法是两个对象之间的优势关系大于某个阈值才把他俩叫有优势, 90分和89分可以近似, 但是90 和100就是优势.

这个优势邻域关系是自反的, 反对称的和传递的.

接下来粒的划分就和优势邻域粗糙集一样了:
\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ ,$x\in U$ and $\delta \ge 0$ .The dominating and dominated neighborhood 
    sets of $x$ w.r.t. $B$ are 
    $$ \begin{aligned}
        \delta_B^+(x)&=\left\{ y\in U\Big|(y,x)\in \delta^\succeq_B \right\}\\ 
        \delta_B^-(x)&=\left\{ y\in U\Big|(x,y)\in \delta^\succeq_B \right\}\\ 
    \end{aligned} $$
\end{defn}

上下近似:
\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ ,$\delta\ge 0$ and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .For 
    any $i\in \left\{ 1,2,\cdots,r \right\}$ ,the lower and upper approximations of $C_i^\succeq$ w.r.t. $B$ are defined as 
    $$ \begin{aligned}
        \underline{\delta}_B^\succeq (C_i^\succeq) &= \left\{ x\in U\Big|\delta_B^+(x)\subseteq C_i^\succeq \right\}\\ 
        \overline{\delta}_B^\succeq (C_i^\succeq)  &= \left\{ x\in U\Big|\delta_B^-(x)\bigcap   C_i^\succeq \ne \varnothing \right\}
    \end{aligned} $$
    The pair $\left( \underline{\delta}_B^\succeq (C_i^\succeq),\overline{\delta}_B^\succeq (C_i^\succeq) \right)$ is called a DNRS of $C_i^\succeq$. 
\end{defn}

同样对于下联合:

\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ ,$\delta\ge 0$ and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .For 
    any $i\in \left\{ 1,2,\cdots,r \right\}$ ,the lower and upper approximations of $C_i^\preceq$ w.r.t. $B$ are defined as 
    $$ \begin{aligned}
        \underline{\delta}_B^\succeq (C_i^\preceq) &= \left\{ x\in U\Big|\delta_B^-(x)\subseteq C_i^\preceq \right\}\\ 
        \overline{\delta}_B^\succeq (C_i^\preceq)  &= \left\{ x\in U\Big|\delta_B^+(x)\bigcap   C_i^\preceq \ne \varnothing \right\}
    \end{aligned} $$
    The pair $\left( \underline{\delta}_B^\succeq (C_i^\preceq),\overline{\delta}_B^\succeq (C_i^\preceq) \right)$ is called a DNRS of $C_i^\preceq$. 
\end{defn}

\subsubsection{混合有序决策系统中基于优势的邻域粗糙集上的属性约简}
首先我们定义几个属性约简相关概念
\begin{defn}[近似精度]
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ ,$\delta\ge 0$ and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .
    The $*-$approximation accuracy of $d$ w.r.t. $B$ is defined as 
    $$ \alpha_B^{(\delta,*)}(D)=\frac{\sum_{i=1}^r|\underline{\delta}_B^\succeq (C_i^*)|}{\sum_{i=1}^r|\overline{\delta}_B^\succeq (C_i^*)|} $$ 
    where $*\in \left\{ \succeq,\preceq \right\}$. 
\end{defn}

较大的$*$-近似精度意味着目标概念的下近似和上近似之间的差异较小。换句话说，$*$-近似精度的值可以反映准则集表征目标概念的能力。

接下来定义约简:

\begin{defn}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ ,$\delta\ge 0$ and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .
    If $\alpha_B^{(\delta,*)}(D)=\alpha_C^{(\delta,*)}(D)$ , where $*\in \left\{ \succeq,\preceq \right\}$ ,then $B$ is a $*-$ approximation
    accuracy set. If $B$ is a $*-$ approximation accuracy consistent set and $\alpha_{B-\left\{ a \right\}}^{(\delta,*)}(D)\ne \alpha_B^{(\delta,*)}(D)$ 
    for any $a\in B$ ,then $B$ is a $*-$ approximation accuracy reduct.
\end{defn}
对于约简来说有等价条件使得约简的条件简化:
\begin{pro}
    Let $(U,C\bigcup\left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ ,$\delta\ge 0$ and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ 
    \begin{enumerate}
        \item $B$ is a $\succeq-$ approximation accuracy consistent set $\iff$ $B$ is a $\preceq-$ approximation accuracy consistent set.
        \item $B$ is a $\succeq-$ approximation accuracy reduct $\iff$ $B$ is a $\preceq-$ approximation accuracy reduct.
        
    \end{enumerate}
\end{pro}

接下来给出属性约简的办法:

\begin{defn}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ and $\delta\ge 0$ .For any $x\in U$ ,we define 
    $$ \begin{aligned}
        l^\delta_B(x) &= \min\left\{ f(y,d)\Big|y\in \delta^+_B(x) \right\},\\ 
        u^\delta_B(x) &= \max\left\{ f(y,d)\Big|y\in \delta^-_B(x) \right\},\\ 
    \end{aligned} $$
\end{defn}


接下来有一条很重要的性质  
\begin{pro}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ , $\delta\ge 0$ and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .
    $\underline{\delta_B^\succeq}(C_i^\succeq)=\underline{\delta_C^\succeq}(C_i^\succeq)$ for any $i\in \left\{ 1,2,\cdots,r \right\}$ iff $l_B(x)=l_C(x)$ for 
    any $x\in U$.  
\end{pro}

对于 $l$ 有这个性质对 $u$ 也有同样的性质 
\begin{pro}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ , $\delta\ge 0$ and $U/\left\{ d \right\}=\left\{ C_1,C_2,\cdots,C_r \right\}$ .
    $\overline{\delta_B^\succeq}(C_i^\succeq)=\overline{\delta_C^\succeq}(C_i^\succeq)$ for any $i\in \left\{ 1,2,\cdots,r \right\}$ iff $u_B(x)=u_C(x)$ for 
    any $x\in U$.  
\end{pro}

接下来构造近似可分辨准则集:

\begin{defn}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS and $\delta\ge 0$. For any $x,y\in U$, the approxmiation descernibility criterion set between $x$ and $y$ is defined as 
    $$ D_\delta(x,y)=\left\{\begin{array}{cl}
        \left\{ a\in C\Big|\Delta_a(x,y)<\delta \right\} & \text{if } l_C^\delta(x)<l_C^\delta(y) \text{ or } u_C^\delta(x)<u_C^\delta(y),\\ 
        \varnothing & \text{otherwise}.        
    \end{array}\right. $$ 
    The family of the approxmiation discernibility criterion sets(ADCSF) is defined as 
    $$ D_\delta=\left\{ D_\delta(x,y)\ne \varnothing\Big|x,y\in U \right\}. $$
\end{defn}

Proposition \ref{pro:1} 通过ADCSF提供了一个近似精度一致集的判断条件.
\begin{pro}\label{pro:1}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$, $\delta\ge 0$ and $D_\delta$ ADCSF.The criterion subset $B$ is a $\succeq-$ approximation 
    accuracy consistent set iff $B\bigcap K\ne \varnothing$ for any $K\in D_\delta$. 
\end{pro}

接下来是ADCSF的最小描述
\begin{coro}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$, $\delta\ge 0$ and $D_\delta$ ADCSF.The criterion subset $B$ is a $\succeq-$ approxmiation
    accuracy consistent set iff $B\bigcap S\ne \varnothing$ for any $S\in MD(D_\delta)$, where $MD(D_\delta)=\left\{ S\in D_\delta\Big|\forall K\in D_\delta\wedge K\subseteq S 
    \implies K=S \right\}$ is referred as MD-ADCSF.
\end{coro}

\begin{coro}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$, $\delta\ge 0$ and $MD(D_\delta)$ the MD-ADCSF. The criterion subset $B$ is a $\succeq-$approximation
    accuracy reduct iff $B$ is the minimal set that satisfies $B\bigcap S\ne \varnothing$ for any $S\in MD(D\delta)$ . 
\end{coro}

接下来就是属性约简的矩阵计算:
首先利用 neighborhood dominance relation (NDR) 构造了一个 boolean 矩阵. 叫做 NDR matrix
\begin{defn}[NDR matrix]
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$ and $\delta\ge 0$.The NDR matrix w.r.t. $B$ is defined as $R_B^{(\delta,\succeq)}=\left( r_{ij} \right)_{n\times n}$,
    where $r_{ij}=1$ if $(x_i,x_j)\in \delta_B^\succeq$, $r_{ij}=0$ otherwise.  
\end{defn}

为了方便通过矩阵去计算 $l_C^\delta(x)$ 和  $u_C^\delta(x)$ , 我们需要首先定义两个矩阵运算: $\oplus,\odot$.
\begin{defn}
    Let $\mathscr{A}=\left( \alpha_{ij} \right)_{n\times n}$ and $\mathscr{B}=\left( \beta_j \right)_{n\times 1}$.
    \begin{enumerate}
        \item $A\oplus B=\left( \gamma_i \right)_{n\times 1}$ ,where 
        $$ \gamma_i=\min\left\{ \left\{ \alpha_{ji}\beta_j\Big|j=1,2,\cdots,n \right\}-\left\{ 0 \right\} \right\} $$
        
        \item $A\odot B=\left( \gamma_i \right)_{n\times 1}$ ,where 
        $$ \gamma_i=\max\left\{ \alpha_{ij}\beta_{j}\Big|j=1,2,\cdots,n \right\} $$
    \end{enumerate}
\end{defn}

接下来就能通过矩阵去计算 $l_C^\delta(x)$ 和  $u_C^\delta(x)$ 了.
\begin{pro}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$, $\delta\ge 0$ , $R_C^{(\delta,\succeq )}=\left( \alpha_{ij} \right)_{n\times n}$ the NDR matrix 
    induced by $C$ , and $\mathscr{H}=\left( f(x_i,d) \right)_{n\times 1}$ the vector representation of $d$ . We have 
    \begin{enumerate}
        \item $l_C^\delta=R_C^{(\delta,\succeq )}\oplus \mathscr{H}$.
        \item $u_C^\delta=R_C^{(\delta,\succeq )}\odot \mathscr{H}$.  
    \end{enumerate}    
\end{pro}

对于 $K\in D_\delta$ 中的元素, 特征向量是 $\mathscr{K}$, 是一个 $m$ 维的列向量. 如果 $a_j\in K$ 那么 $\mathscr{K}$ 的第 $j$ 列就是 $1$ , 否则是 0.
\begin{defn}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$, $\delta\ge 0$ and $D_\delta=\left\{ K_1,K_2,\cdots,K_s \right\}$ the ADCSF.
    The matrix representation of $D_\delta$ is $\mathscr{M}(D_\delta)=\left( \mathscr{K}_1,\mathscr{K}_2,\cdots,\mathscr{K}_s \right)^T$ , where 
    $\mathscr{K}_i$ is the characteristic vector of $K_i$ .
\end{defn} 

接下来从 $\mathscr{M}(D_\delta)$ 诱导出两个矩阵:

\begin{pro}
    Let $(U,C\bigcup \left\{ d \right\},V,f)$ be an HODS, $B\subseteq C$, $\delta\ge 0$ and $D_\delta=\left\{ K_1,K_2,\cdots,K_s \right\}$ the ADCSF, and 
    $\mathscr{M}(D_\delta)=\left( \mathscr{K}_1,\mathscr{K}_2,\cdots,\mathscr{K}_s \right)^T$ the matrix  representation of $D_\delta$.
    \begin{enumerate}
        \item $\mathscr{M}(D_\delta)\cdot (\mathscr{M}(D_\delta))^T=\left( |K_i\bigcap K_j| \right)_{s\times s}$.
        \item $1_{s\times m}\cdot \left( \mathscr{M}(D_\delta) \right)^T=(\alpha_{ij})_{s\times s}$, where $\alpha_{ij}=|K_j|$.   
    \end{enumerate}  
\end{pro}


有了 $MD(D_\delta)$ 后, 我们就可以构造辨识公式 
$$ F_\delta=\bigwedge\left\{ \bigvee\left\{ a\Big|a\in S \right\}\Big|S\in MD(D_\delta) \right\} $$

化简成析取范式 
$$ F_\delta=\bigvee_{k=1}^p\left( \bigwedge_{s=1}^{q_k}a_s \right) $$
则 $B_k=\left\{ a_s\Big|s=1,2,\cdots,q_k \right\}$ 就是所有的约简

\begin{framed}
    这一篇文章基本内容就结束了, 主要思想还是构造辨识矩阵导出辨识公式从而化简为析取范式去求约简, 这是在信息系统与知识发现 \cite{张文修2003信息系统与知识发现} 里面经常要用到的方法.
    这种方法有理论依据并且可以求出所有的约简, 比起启发式算法来说更适合理学.    
\end{framed}
